//************************************************************
//    > File Name: valid-parentheses.cpp
//    > Author: davis
//    > Mail:  
//    > Created Time: 2017年03月21日 13:28:38
//***********************************************************
//lintcode #423
#include<bits/stdc++.h>
using namespace std;
bool isValidParentheses(string& s){
	stack<char> parentheses;
	for(int i=0;i<s.length();++i){
		if(s[i]=='(' || s[i]=='[' || s[i]=='{')
			parentheses.push(s[i]);
		else if(parentheses.size()){
			if(s[i]==')' && parentheses.top()=='('){
				parentheses.pop();
				continue;
			}
			if(s[i]==']' && parentheses.top()=='['){
				parentheses.pop();
				continue;
			}
			if(s[i]=='}' && parentheses.top()=='{'){
				parentheses.pop();
				continue;
			}
			else
				return false;
		}
		else false;
	}
	return !parentheses.size();

}
bool isValidParentheses2(string& s) {
	const  unordered_map<char, char> symbol_pair = {{')', '('},
		{']', '['},
		{'}', '{'}};
	stack<char> parentheses;
	for (const auto& c: s) {
		const auto& it = symbol_pair.find(c);
		if (it != symbol_pair.cend()) {
			if (parentheses.empty() ||
					parentheses.top() != it->second) {
				return false;
			}
			parentheses.pop();
		} else {
			parentheses.emplace(c);
		}
	}
	return parentheses.empty();
}

int main(){
	string s="({}[(])()";
	bool is=isValidParentheses2(s);
	cout<<is<<endl;
}
